﻿#define _CRT_SECURE_NO_WARNINGS 1

using namespace std;
// 原题连接：https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

/*
题目描述：
描述
你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为
�
�
v
i
​
  ,价值为
�
�
w
i
​
 。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数
�
�
v
i
​
 和
�
�
w
i
​
 ，表示第i种物品的体积和价值。
1
≤
�
,
�
≤
1000
1≤n,V≤1000

输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
示例1
输入：
2 6
5 10
3 1
复制
输出：
10
2
复制
示例2
输入：
3 8
3 10
9 1
10 1
复制
输出：
20
0
复制
说明：
无法恰好装满背包。
示例3
输入：
6 13
13 189
17 360
19 870
14 184
6 298
16 242
复制
输出：
596
189
复制
说明：
可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.
*/

#include <iostream>
#include <vector>

using namespace std;

// 开始解题：
// 方法——动态规划
int main() {
    int n = 0, V = 0;
    cin >> n >> V;
    vector<int> v(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    // 解决问题一


    // 创建dp表
    vector<int> dp(V + 1);
    // 初始化(省略)

    // 填表
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= V; j++) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    cout << dp[V] << endl;
    // 解决问题二

    for (int j = 0; j <= V; j++) {
        dp[j] = 0;
    }

    // 初始化
    for (int i = 1; i <= V; i++) {
        dp[i] = -1;
    }

    // 再次填表
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= V; j++) {
            if (dp[j - v[i]] != -1) {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
    }
    if (dp[V] == -1) {
        cout << 0 << endl;
    }
    else {
        cout << dp[V] << endl;
    }
    return 0;
}